#include <stdio.h>

int max_sub_array(int a[], int s, int e,  int *l, int *r) {
    int ll, lr; //左数组的最大子数组的左右起点
    int rl, rr; //右数组的最大子数组的左右起点
    int lsum, rsum; //左右数组的最大子数组的和
    int i;
    int lrsum = 0, mlrsum, rlsum = 0, mrlsum, lrl, rlr; 
    if(s==e) {
        *l = *r = s;
        return a[s];
    }else if(s < e){
        int mid = (s+e)/2;
        lsum = max_sub_array(a, s, mid, &ll, &lr);
        rsum = max_sub_array(a, mid+1, e, &rl, &rr);
        mlrsum = a[mid];
        lrl = mid;
        for(i=mid; i>=s; i--) {
            lrsum += a[i];
            if(lrsum > mlrsum) {
                mlrsum = lrsum;
                lrl = i;
            }

        }
        mrlsum = a[mid+1];
        rlr = mid+1;
        for(i=mid+1; i<=e; i++) {
            rlsum += a[i];
            if(rlsum > mrlsum) {
                mrlsum = rlsum;
                rlr = i;
            }
        }
        int midsum = mrlsum + mlrsum;
        if(midsum >= lsum && midsum >= rsum) {
            *l = lrl;
            *r = rlr;
            return midsum;
        }else if(lsum >= midsum && lsum >= rsum) {
            *l = ll;
            *r = lr;
            return lsum;
        }else {
            *l = rl;
            *r = rr;
            return rsum;

        }

    }
}

int l_max_sub_array(int a[], int n, int *l, int *r) {
    int i,j;
    int rl=0;
    *l = *r = 0;
    int rlsum = a[0];
    int msum = a[0];
    for(i=1; i<n; i++) {
        if(rlsum >0 ) {
            if(rlsum + a[i] > msum) {
                *l = rl;
                *r = i;
                msum = rlsum+a[i];
            }
            rlsum += a[i];

        }else {
            rl = i;
            rlsum = a[i];
            if(a[i] > msum) {
                *l = *r = i;
                msum = a[i];
            }
        }    
    
    }
    return  msum;

}


int main(void)
{
    int a[] = {-1, -2, -3, -4, -5, -3, -4, -1, -6};
    int l, r;
    int msum = max_sub_array(a, 0, 8, &l, &r);
    printf("msum:%d, l:%d, r:%d\n", msum, l, r);
    msum = l_max_sub_array(a, 9, &l, &r);
    printf("msum:%d, l:%d, r:%d\n", msum, l, r);

}
